You are not logged in. Please login at www.codechef.com to post your questions!

×

[closed] Data Structure Tutorial : Stack

Overview:
Stack is data structure where elements is inserted at the top of the list and any element is deleted from the top of list. So it is called LIFO data structure. Insert operation on a stack is often called push and delete operation is often called pop.

The following picture top is an indicator that indicates the top element of the stack. alt text

Real life applications of stack:
There are many real life example of stack. In our daily life, we see stack of plates in cafeteria or restaurant, stack of the books in book shop. The palate which is at the top is the first one to deleted. Similarly the plate which is at the bottom most is the last one to be deleted.

Operation :
The following operation are performed in the stack.
1. Push : To add an element to a stack.
2.Pop : To remove an element from the stack.
3.Peek : To get the topmost element.

Implementation :
Stack can be implemented two ways. using array and using linked list.Here we discuss stack implementation using array. The stack which is implemented using array array is called array based stack. It uses top variable to print the top most element in the linear array.

1. Initially top=0
2. In Push operation top is increased by one and pushed item to stack[top]
3. In Pop operation top decrease.
4. In Peek operation check that the top is not zero and return stack[top].

 Algorithm : Push(stk, n, item)                
 Step 1: Start         
 Step 2: if(top==n)        print overflow          
         else              stk[top++]=item.           
 Step 3: End

C++ implementation :
void push(int stk[],int n, int item)
{
   if(top==n)  cout<<"Overflow"<<endl;
   else        stk[top++] = item;
}


 Algorithm : Pop(stk)
 Step 1: Start
 Step 2: if(top==NULL)  print Underflow;
         else           top--;
 Step 3: End
C++ implementation :
void pop(int stk[] )
{
   if(top==NULL)    cout<<"Underflow"<<endl;
   else             top-- ;
}

 Algorithm : Peek(stk)
 Step 1: Start
 Step 2: if(top==NULL)  print Underflow;
         else           return stk[top-1];
 Step 3: End
C++ implementation :
int peek(int stk[] )
{
   if(top==NULL)    cout<<"Underflow"<<endl;
   else             return skt[top-1];
}

Stack has many application . We can convert an infix into post-fix expression using stack. We can explain this. We start to scan the expression from left to right. In an expression , there may be some operands, operators and parenthesis.

Steps:
 1. If a symbol is an operand add it to the post-fix expression.

 2. If the symbol is an opening parenthesis push it on the stack.

 3. If the symbol is an operator.Then check the top of the stack. 
   (i) If the precedence of the operator at the top is higher or same as the current operator     then repeatedly it is popped and added to the post-fix expression.
  (ii) Else it pushed onto the stack.

 4.If the symbol a closing parenthesis then
   (i) Repeatedly pop from the stack and add each operator to the postfix expression  until the corresponding opening encountered.
  (ii) Remove the opening parenthesis from the stack.
C++ implementation :
   void prefex2postfix(string s)
   {
      stack<char>st;
      for(int i=0; i<s.length(); i++)
       {
          if(isdigit(s[i]) || isalpha(s[i]))  cout<<s[i];
          else if( s[i]==')' )
          {
             while(st.top()!='(')
             {
                    cout<<st.top();
                    st.pop();
             }
             st.pop();
          }
          else st.push(s[i]);
       }
    }

Stack full source code : link

Codechef Problem : ONP , BEX
Spoj Problem STPAR , Transform the Expression
Hackerrank : Balanced Brackets

asked 21 Nov '16, 21:30

rashedcs's gravatar image

2★rashedcs
49751755
accept rate: 4%

closed 01 Jan '17, 11:43

The question has been closed for the following reason "Other" by rashedcs 01 Jan '17, 11:43


Have you checked your implementations in C++? There are quiete a few rather obvious issues and at least one serious non-obvious bug ( hint: what is the meaning of the variable top? are both push and pop consistent?)

link

answered 22 Nov '16, 03:28

ceilks's gravatar image

7★ceilks
1.8k9
accept rate: 36%

Yeap. top is an indicator that indicates the top element of the stack.I think both are consistent.

(22 Nov '16, 10:13) rashedcs2★
4

Not exactly. IN your algorithm top is always (1+the index of the topmost element on the stack). So both both stk[top] in peek and stk[top--] in pop are evaluating the underlying array at the unfilled position above the top element.

(22 Nov '16, 15:06) ceilks7★

Now check please. I edited my post.

(23 Nov '16, 16:43) rashedcs2★

What does stk[top--] mean?

link

answered 22 Nov '16, 08:59

mathecodician's gravatar image

6★mathecodician
2.6k1933
accept rate: 7%

And also stk[top++]

(22 Nov '16, 09:29) mathecodician6★

stk[top++]=item means to top is increased by one and pushed item to stack[top].

Similarly stk[top--] means to top is decreased by one.

(22 Nov '16, 10:16) rashedcs2★

What is postfix and infix?

link

answered 22 Nov '16, 09:00

mathecodician's gravatar image

6★mathecodician
2.6k1933
accept rate: 7%

If the operator is placed in the middle it is known as infix. Similarly, If the operator is placed after the two operands it is known as infix.

Infix : A+B Postfix : AB+

(22 Nov '16, 10:21) rashedcs2★

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×843

question asked: 21 Nov '16, 21:30

question was seen: 1,266 times

last updated: 01 Jan '17, 11:43