Thank you for the replies. Appreciate it
My understanding was that you can perform only push and pop operation on the stack but today we were asked to write a function that would search for a given element in the stack and return it if it exists. This left me confused
Wouldn't stack be usually implemented when the LIFO order must be strictly followed? Assuming that's the case, if I want to search the stack for a particular element, the best practice would be to pop the contents until the desired element is found and then push them back onto the stack in their original order, correct? And if I do that, wouldn't it be more convenient to store the popped elements in a separate array since having two stacks would get kind of redundant? Or am I missing something here?
Also, is there a data structure generally preferred for implementing stack or is it just a matter of one's preference?
//Mechanism of Stack data structure implemented in JAVA
public class newStack {
private int[] testArr ;
private int size;
private int first ;
public newStack(int s) {
size = s;
testArr = new int [size];
first = -1;
}
public void push(int m) {
testArr[++first] = m;
}
public int pop (){
return testArr[first--];
}
public int peek() {
return testArr[first];
}
public boolean isEmpty(){
return (first == -1);
}
public boolean isFull(){
return (first == size - 1);
}
}// Test Code of stack implementation
import java.util.Scanner;
public class StackTest {
public static void main (String args []){
newStack stack = new newStack(10);
Scanner in = new Scanner(System.in);
System.out.println("Enter the desired values max upto arraysize:");
while (!stack.isFull()){
stack.push(in.nextInt());
}
while(!stack.isEmpty()){
int n = stack.pop();
System.out.print(n);
System.out.print(" ");
}
System.out.println("");
}
}#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define STACK_SIZE 10
int contents[STACK_SIZE];
int top;
void init( void ); // Initializes the stack.
bool isEmpty( void ); // Returns true if the stack is empty.
bool isFull( void ); // Returns true if the stack is full.
void Push( int i ); // Pushes an element onto the stack.
int Pop( void ); // Pops an element off the stack.
bool search( int ); // Searches the stack for a given element and returns true if it exists.
int main(int argc, char const *argv[])
{
int i, key;
// Create a stack
init();
// Populate the stack with a few elements
for (i = 0; i < STACK_SIZE; i++)
Push(i);
printf("Enter element to search: \n");
scanf("%d", &key);
if (!search(key))
printf("Element not found"); // search returned false.
else
printf("Element found"); // searched returned true.
fflush(stdin);
getchar();
return 0;
}
void init( void )
{
top = 0;
}
bool isEmpty( void )
{
return top == 0;
}
bool isFull( void )
{
return top == STACK_SIZE;
}
void Push( int val )
{
if ( isFull() ) {
printf("Stack Overflow\n");
exit(1);
}
contents[top++] = val;
}
int Pop( void )
{
if ( isEmpty() ) {
printf("Stack underflow\n");
exit(1);
}
return contents[--top];
}
bool search( int key )
{
if ( isEmpty() ) {
printf("Stack is Empty\n");
exit (1);
}
while ( !isEmpty() ) {
if (Pop() == key)
return true;
}
return false;
}bool search( int key )
{
int found = false;
int count = 0;
int temp[STACK_SIZE];
if ( isEmpty() ) {
printf("Stack is Empty\n");
exit (1);
}
while ( !isEmpty() ) {
if ( (temp[count++] = Pop()) == key) {
found = true;
break;
}
}
while ( !isFull() )
Push(temp[--count]);
return found;
}Exactly. Why would you want to search a stack? And in fact, I did ask my teacher that question. She just gave me the look and said it's fine if you have to do it, there's nothing wrong with it. Well, whatever. For now, I'll just do it with the function I posted in post #8 which maintains the LIFO structure.Slightly fixed the push and pop methods.
In push(), the top is incremented first and then a value is assigned.
In pop, the top is simply decremented. The underflow check condition is good.
Now coming to the main part, the search function is kind of unnecessary in a stack. I don't know why your teacher is encouraging you to even try it.
I mean what's the point really?
Suppose you have the required key at "n" index, you have to pop each and every element out of the stack upto "n" element, in order for a match.
So you are doing n pops basically. If the nth value is big i.e 100 or more, then you've to do 100 pops or more to find the key. Its simple linear search and is inefficient.
Stacks are never designed for any searching purpose.
If you want efficient search algorithm, try binary search. Also ask your teacher why they are encouraging to search a key from a stack.
You can use stacks for more practical purposes like reversing a string. Notice what happens when you pop elements out of a stack. Aren't the order reversed?