[Note: Visit cPlusPlus.psexam.com for exam­ples and source code of C++ imple­men­ta­tion of Stacks Data Struc­ture. Click Here]

Today its turn of Stacks. In our pre­vi­ous posts we’ve dealt a bit about Data Types, Data Struc­tures and Abstract Data Types, A list of dif­fer­ent data struc­tures in use in pro­gram­ming world, List data struc­ture, Linked list data struc­ture and com­pared lists with arrays. If you have missed, its good to go back and check the pre­vi­ous posts for them.

Fol­low­ing Com­puter Offi­cer syl­labus of Pub­lic Ser­vice Com­mis­sion, we are at the end on topic 2.2

Let’s col­lect the bits now!

What is a Stack?

A stack is a spe­cial type of list, where only the ele­ment at one end can be accessed. Items can be “pushed” onto one end of the stack struc­ture. New items are inserted before the oth­ers, as each old ele­ment moves down one posi­tion. The first ele­ment is referred to as the “top” item, and is the only item that may be accessed at any time. In order to access items that are fur­ther down the stack, they must be moved to the top by “pop­ping” the appro­pri­ate num­ber of items. Pop­ping refers to remov­ing the top ele­ment of a stack. This is referred to as a LIFO struc­ture, “Last In, First Out”.

These rules make stacks very restricted in use, how­ever they are very effi­cient and much eas­ier to imple­ment than lists. The uses of stacks vary from pro­gram­ming a sim­ple card game, to main­tain­ing the order of oper­a­tions in a com­plex pro­gram. For exam­ple, a stack is use­ful in a man­age­ment pro­gram where the newest tasks must be exe­cuted first. The node of a stack is usu­ally pre­sented with the fol­low­ing struc­ture, which is very sim­i­lar to that of a list node.

Source ThinkQuest [visit the page for exam­ple codes]

A stack is a last in, first out (LIFO) abstract data type and data struc­ture. A stack can have any abstract data type as an ele­ment, but is char­ac­ter­ized by only two fun­da­men­tal oper­a­tions: push and pop. The push oper­a­tion adds to the top of the list, hid­ing any items already on the stack, or ini­tial­iz­ing the stack if it is empty. The pop oper­a­tion removes an item from the top of the list, and returns this value to the caller. A pop either reveals pre­vi­ously con­cealed items, or results in an empty list.
A stack is a restricted data struc­ture, because only a small num­ber of oper­a­tions are per­formed on it. The nature of the pop and push oper­a­tions also means that stack ele­ments have a nat­ural order. Ele­ments are removed from the stack in the reverse order to the order of their addi­tion: there­fore, the lower ele­ments are typ­i­cally those that have been in the list the longest.

Source Wikipedia

Stack Oper­a­tion

Besides the push and pop oper­a­tions on a stack, it is desir­able to have at least two more: an ini­tial­ize oper­a­tion, which pre­pares the stack for use and sets it to an empty state, and an empty oper­a­tion which is sim­ply a test to see whether the stack is empty. The empty oper­a­tion is use­ful to guard against an attempt to pop an empty stack, which is an error.

Push: Add an item to the top of the stack
pop: remove an item from the top of the stack
empty: test whether the stack is empty
full: test whether the stack is full
ini­tial­ize: set up the stack in an empty condition

Source: Data Strucutres and Algo­rithms by Shi-Kuo Chang

Where Stacks can prove be useful

• Con­ver­sion of arith­metic expres­sions (infix, pre­fix, postfix)
• Eval­u­a­tion of arith­metic expres­sions. Con­vert the expres­sion in post­fix nota­tion and imple­ment stack to evaluate.
• Stacks are use­ful for recur­sive solu­tions like find­ing factorial.
• Clas­sic com­puter sci­ence prob­lem 8-queens prob­lem can be solved by using stacks.
• Stacks are very help­ful to decid­ing whether some pair of expres­sion delim­iters are prop­erly paired, even if they are embed­ded mul­ti­ple pairs deep.
• Stacks can be extremely use­ful to reverse the list items.
• One use­ful appli­ca­tion of stack is to sort a num­ber of data using quick sort algorithm.

Sources:

C++ Data Struc­tures: A Lab­o­ra­tory Course
by Ste­fan Bran­dle, Jonathan Geisler, james Roberge

Clas­sic Data Struc­tures by D. Samanta

Stacks Rep­re­sen­ta­tion

Stacks can be imple­mented as:

• Array rep­re­sen­ta­tion
• Linked List representation

We’ll be dig­ging more on stacks in com­ing posts. Till then, happy learning!

[Note: Visit cPlusPlus.psexam.com for exam­ples and source code of C++ imple­men­ta­tion of Stacks Data Struc­ture. Click Here]

No related posts.

Related posts brought to you by Yet Another Related Posts Plu­gin.