Talk:Stack (abstract data type)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated C-class, High-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
C-Class article C  This article has been rated as C-Class on the project's quality scale.
 High  This article has been rated as High-importance on the project's importance scale.
 

Rename[edit]

I think this article should be named stack (computer science) since the concept of stack is used other than making computer software? Any objection? -- Taku 00:47, 6 Sep 2003 (UTC)

Stack (computing)? Nice, generic term... Includes CS and software dev't too. Dysprosia 00:49, 6 Sep 2003 (UTC)
It is fine too. Any other thoughts?

Merge[edit]

(to Martin) Hi, I see you merged stack pointer into Stack. Are you sure it's not an important enough idea to merit a separate article? There are a number of pages that link to stack pointer (and I was about to add a few more :-). Noel 20:04, 18 Oct 2003 (UTC)

Prove me wrong and write a long and well-written article on a stack pointer if you like.. but the version I merged didn't seem worth a seperate article. Martin 22:29, 20 Oct 2003 (UTC)

Image[edit]

I made an image for the german pendant to a stack (de:Kellerspeicher), perhaps you want to include it here. Is there a possibility to reuse the one from there or does it need a second upload? TRauMa, 2003-11-26

Stack demo.png

I made my own stack image because I have a hard time seeing the one that is currently in the article (the contrast of the different shades of blue makes it hard for me to see the edges). The different layers are slightly transparent to make it more apparent that there are different layers. Is this acceptable? [[User:Aranel|Aranel ("Sarah")]] 17:27, 25 Oct 2004 (UTC)

LIFO / FIFO ?[edit]

Are all stacks LIFO? Aren't there FIFO stacks too? BradGad (Talk) 21:55, 21 Mar 2005 (UTC)

A "FIFO stack" would be a queue, I believe. anetor 07:45 07 Apr 2005 (PDT)
"FIFO" refers to a queue. cslave 21 Sept 2005

Stack (computing) merge with Stack-Based Memory Allocation[edit]

I believe Stack-Based Memory Allocation should be merged into this article because most of the information is redundant. Thoughts? --Vanished user 1029384756 15:08, 2 August 2005 (UTC)

Agreed. -- Taku 22:58, August 2, 2005 (UTC)
I Second -- cslave 21 Sept, 2005
The Stack-Based Memory Allocation article is total crap and should be deleted. -- John Tsiombikas 15 oct. 2005
Stack-Based Memory Allocation is an architecture article and thus is juxtaposed against Heap-Based Memory Allocation. The article here is about a more implementation-free stack and Stack machine describes a stack as a device unto itself. All three perspectives are useful, and Stack pointer aligns more with the architechture area. Hackwrench 01:38, 6 November 2005 (UTC)

Rotate method?[edit]

What is this rotate method for? What languages implement it? its not in the standard java lib...

Stack manipulation beyond pushing and popping is very useful in stack-oriented languages. Also, some dialects of Lisp will rotate on lists. Tsowell 11:40, 10 October 2006 (UTC)
The rotation visualization is confusing because it uses the same values in what look like different positions to contrast the visualization. The stack data is described by numerical position and the right-rotate process is described as, "right rotate will move the first element to the third position, the second to the first and the third to the second". A purely numerical representation of data items in a stack could be viewed as insufficient because the positions and the data items would both be represented numerically, thus easily confusing the reader. While the visualization IS equivalent, it is overly complex because it requires the reader to decipher the initial positioning by comparing the two data flows without indication of top to bottom or right to left priorities.
This is the current example:
apple                                                       banana
banana                 ==right rotate==>     cucumber
cucumber                                                apple 
and
cucumber banana apple  ==right rotate==>  apple cucumber banana
Pure numeric representation would work as long as the article stated that the numbers were values within the stack and not indicative of the actual address within the stack. So the examples could be:
Bottom Up (Top to bottom):
1                           2
2 right rotate =>  3
3                           1
Left to Right:
3 2 1 == right rotate == > 1 3 2
Both of the designations in the paragraph above the visualization become misleading without an indication of direction. When most people think about left to right they assume they will read 0 1 2 3 from left to right on the page. The same applies to the term bottom up.
As defined in the article, the first and second positions rotate, then the second and third positions rotate. An animated diagram may be better.
As it is, ROL 1 2 3 > 2 3 1 works fine for the example, but when you get into a larger stack what happens? Does 1 2 3 4 5 6 rotate each item in series? 2 3 4 5 6 1 ?
Why not define it as: "Right Rotate moves the first item to the last position". If it functions as described it will always do that. The fact that it seems to be explained in terms of a sequential rotation involving two items at a time with the accompanying visualizations seems like a way to make the simple overly complex.
An example using the 6502 processor (motorola) is found here: http://www.atariarchives.org/roots/chapter_9.php (that would also cover early Apple Machines).

Peak?[edit]

Is this anything more than a falsely-justified spelling error? I can't find any such usage on Google. "Top", on the other hand, is a fairly widely-used alternative to "peek". Tsowell 11:40, 10 October 2006 (UTC)

As stated, the term 'peak' isn't a spelling error. Here is source found on the second page of google, searching for 'stack peak': http://www-db.stanford.edu/~burback/containers/stack.cpp
The function is meant to show the peak (top, acme, etc) of the stack without removing and returning it.
There have been many terms used to describe this, I prefer 'peak', but if you feel 'top' should be added, I wouldnt' have any objections.
On an off note, I do ask that people not edit things to change 'peak' to 'peek', since 'peak' is mentioned, it is a bit of an inane edit.
Reikon 23:02, 16 October 2006 (UTC)
Methods/functions are, by convention, verbs, just as objects are nouns. Therefore, 'peek' is better than 'peak' or 'top'. 'peak' also suggests a root of a tree (peak of a mountain?) to some in my experience. --David Federman 05:27, 24 November 2006 (UTC)
I strongly prefer peek to peak. I learned peek and top 20 years ago but this is the first time I've seen peak. When I Google'd (before reading this discussion) I found the stanford/burback source listed above - and I think it is a spelling error. I vote for peek as the primary spelling, with top (long established) and peak (reluctantly) as alternates. Manassehkatz 03:25, 4 December 2006 (UTC)
I found a textbook reference to TOP and adjusted the page accordingly. If anyone can find a citation (not just code on a webpage) earlier than 1984 showing PEEK or PEAK, please feel free to change. I also changed the pseudocode to pass data elements rather than nodes (data + pointer) as the push/pop/top functions should hide the pointer implementation details. Manassehkatz 15:31, 4 December 2006 (UTC)
Frankly, I've always appreciated peek (in this context) as meaning : look but don't touch anything which makes it a lot easier to explain to a student. Colin meier (talk) 18:28, 27 March 2009 (UTC)

JVM[edit]

Does anyone else think that the mention of the JVM in the intro paragraph is a bit excessive? It makes it sound like the JVM is some integral low-level part of the OS. —Preceding unsigned comment added by 209.234.66.97 (talkcontribs) 07:02, November 26, 2006 (UTC)

The pop operation[edit]

It is stated that pop removes and returns the top element. This violates good design practice that inspection (return the top element) and mutation (remove the top element) should not be in the same operation. I suggest that the operation "top" return (a copy of) the top element and that the operation "pop" removes the top element without returning it. Comments? Corpus gigantus 07:19, 25 September 2007 (UTC)

Usually the elements are not "removed" or "deleted" anyway, the stack pointer is just decremented, as deleting is too wasteful of a computers resources... —Preceding unsigned comment added by 86.29.36.156 (talk) 23:20, 12 May 2008 (UTC)

Stacks usually grow down[edit]

In 28 years of programming Ive always known that stacks grew downwards and not upwards. This is certainly the case with many processors. With Rockwells 6500 family the stack always grew downwards and certainly when it comes to iPX86 upwards the stack grows downwards. It might only be semantics but it would be nice for the main page to be correct. —Preceding unsigned comment added by 83.146.9.122 (talk) 01:25, 11 November 2007 (UTC)

Stacks grow upwards like piling up of books, don't they? KnowledgeHegemonyPart2 (talk) 06:44, 3 April 2008 (UTC)


If I'm teaching students to implement stacks in arrays, etc, those stacks grow upward. I think currently upwards or downwards will depend on the implementation.Colin meier (talk) 18:30, 27 March 2009 (UTC)
Stacks can grow either up or down; in my 41 years of programming I've encountered both scenarios, even with different languages on the same hardware. It depends to some extent on what useful hardware instructions and addressing modes are available (if any). There are two hardware instructions which may be significant in determining this choice: (a) machine-level subroutine call instruction, or (b) instruction used to push contents of a register onto a stack. The available addressing modes may also be significant: if offsets from a base register must be positive then it is easier to have the stack grow upwards, but if offsets can be both negative and positive then the stack could just as easily grow in either direction. Murray Langton (talk) 04:32, 30 March 2009 (UTC)

Qustion[edit]

Can we run any program without stack? —Preceding unsigned comment added by 77.237.75.252 (talk) 03:18, 24 April 2008 (UTC)

Yes, but you couldn't use Structured programming techniques... —Preceding unsigned comment added by 86.29.36.156 (talk) 23:18, 12 May 2008 (UTC)

Postfix[edit]

  1. include <stdio.h>
  2. include <conio.h>
  3. include <string.h>
  4. include <ctype.h>
  1. define MAX 50

char stack[MAX] ; char infix[MAX] ; char postfix[MAX] ; char eval[MAX] ; char *s, *t ; /*pointers to input and output strings*/ int top; /*Stack top*/

/*Function Prototypes*/ void Initialize (void); void SetExpression (char *); char Pop (void ); void Push (char); int priority (char); void Convert (void); int Evaluate(void);

void main( ) { int m;

clrscr( ) ; Initialize ( ) ; printf ( "\nEnter an infix expression: " ) ; gets ( infix ) ; SetExpression (infix) ; Convert( ) ; printf ( "\nThe Postfix expression is: " ) ; puts(postfix); strcpy(eval,postfix); m=Evaluate( ); printf("answer: %d", m );

getch( ) ; }

void Initialize (void) { top = -1 ;/*Make stack empty*/ }

void SetExpression ( char *str ) { s = str ; t = postfix; }

/* adds operator to the stack */ void Push ( char c ) { if ( top == MAX - 1 ) printf ( "\nStack is full.\n" ) ; else { top++ ; stack[top] = c ; } }

/* pops an operator from the stack */ char Pop ( void ) { if ( top == -1 ) /* Stack is empty*/ return -1 ; else { char item = stack[top] ; top-- ; return item ; } }

int priority(char c) { if ( c == '*' || c == '/' || c == '%' ) return 2; else if ( c == '+' || c == '-' ) return 1; else return 0; }

/* converts the infix expr. to postfix form */ void Convert (void) { char x ;

while ( *( s ) ) { /*Skip white spaces, if any*/ if ( *( s ) == ' ' || *( s ) == '\t' ) { s++ ; continue ; }

if ( isdigit ( *( s ) ) )/*Operands*/ { while ( isdigit ( *( s ) ) ) {

  • ( t ) = *( s ) ;

s++ ; t++ ; } } if ( *( s ) == '(' )/*Opening Parenthesis*/ { Push ( *( s ) ) ; s++ ; } if ( *( s ) == '*' || *( s ) == '+' || *( s ) == '/' || *( s ) == '%' || *( s ) == '-' ) /*operators*/ { if ( top != -1 ) { x = Pop ( ) ; while ( priority ( x ) >= priority ( *( s ) ) ) {

  • ( t ) = x ;

t++ ; x = Pop ( ) ; } Push( x ) ; Push ( *( s ) ) ; } else Push( *( s ) ) ; s++ ; } if ( *( s ) == ')' )/*Closing Parenthesis*/ { x = Pop ( ) ; while ( x != '(' ) {

  • ( t ) = x ;

t++ ; x = Pop ( ) ; } s++ ; } } while ( top != -1 )/*While stack is not empty*/ { x = Pop ( ) ;

  • ( t ) = x ;

t++ ; } t++ ; }

int Evaluate(void) { int i,l,a,b,q,z; l=strlen(eval); for(i=0;i<l;i++) { if ( isdigit ( eval[i] ) ) { Push(eval[i]); } else if ( eval[i] == '*' || eval[i] == '+' || eval[i] == '/' || eval[i] == '%' || eval[i] == '-' ) { a = Pop ( ); b = Pop ( );

switch( eval[i] ) { case '+' : q=b+a; break; case '-' : q=b-a; break; case '*' : q=b*a; break; case '/' : q=b/a; break; } Push ( q ); } } z = Pop ( ); return z; }

Convoluted[edit]

Any particular reason for using overly complicated code to illustrate what is really a very simple idea? There are plenty of examples on the web that illustrate a stack implementation in simpler terms. How about using an array based example that just stacks doubles (I'm avoiding the use of ++ operators because not everyone is familiar with the notation) ?

#define MAXSTACK 10
#define EMPTYSTACK -1
 
int top = EMPTYSTACK;
double items[MAXSTACK];
 
void push(double value) {
   top = top + 1;
   items[top] = value;
}
 
double pop() {
   int value = items[top];
   top = top - 1;
   return value;
}
 
double peek() {
  return items[top];
}
 
int full()  {
   return top == MAXSTACK - 1;
}


Lack of Abstraction[edit]

Considering a stack is a fundamental computer science data structure there seems to be a great lack of abstraction in this article. Shouldn't we define what a stack is before we start plunging into implementations?

/Definition/

Function signatures:

  init: -> Stack 
  push: N x Stack -> Stack 
  top: Stack -> (N U ERROR) 
  remove: Stack -> Stack 
  isempty: Stack -> B 


(where N indicates a element (natural numbers in this sace), B indicates a boolean and U indicates set union)


Semantics

  top(init()) = ERROR 
  top(push(i,s)) = i 
  remove(init()) = init() 
  remove(push(i, s)) = s 
  isempty(init()) = true 
  isempty(push(i, s)) = false 

Jones "Systematic Software Development Using VDM"

ps. is there a bug with the wiki editor- none of the buttons work...

Salocin-yel (talk) 08:18, 7 June 2010 (UTC)

File:Towers of Hanoi.jpeg Nominated for Deletion[edit]

Image-x-generic.svg An image used in this article, File:Towers of Hanoi.jpeg, has been nominated for deletion at Wikimedia Commons in the following category: Media without a source as of 17 September 2011
What should I do?

Don't panic; a discussion will now take place over on Commons about whether to remove the file. This gives you an opportunity to contest the deletion, although please review Commons guidelines before doing so.

  • If the image is non-free then you may need to upload it to Wikipedia (Commons does not allow fair use)
  • If the image isn't freely licensed and there is no fair use rationale then it cannot be uploaded or used.

This notification is provided by a Bot --CommonsNotificationBot (talk) 15:46, 17 September 2011 (UTC)

The "Applications" section should be split.[edit]

It's far too long and it looks like splitting it up could be done at the same time as general cleanup. I'll go through each sub-section...

6.1 Converting a decimal number into a binary number
This could probably stay, it's fairly short.
6.2 Towers of Hanoi
The bulk of this should be moved into Towers of Hanoi and/or merged with the algorithms described there. A few paragraphs describing the problem and why stacks are applicable to it should be left on this page, with a "main article" template link.
6.3 Expression evaluation and syntax parsing
I haven't looked around for a page on this subject, but there probably is one; if not, there deserves to be one! It can then be summarized again in a few paragraphs with a "main article" template link to the existing/new page.
6.4 Conversion of an Infix expression that is fully parenthesized into a Postfix expression
This sub-section could be merged with the existing/new page that the content under 6.3 would be moved to.
6.5 Rearranging railroad cars
This seems short enough to keep on this page.
6.6 Quicksort
This should be moved/merged with the Quicksort page, again with a summary and main article link.
6.7 The Stock Span Problem
I'm not well versed in this subject, but it seems like another thing that could be moved to either a new page or an existing one, again with a summary and main article link.
6.8 Runtime memory management
This is already summarized and main article linked, so it can be left as is. This is how most of the other sections should ideally be.

I'm putting this here rather than actually doing it because it's a huge amount of work and should probably be discussed further before anything is done, to avoid doing anything that would turn out to be unnecessary in the long run, and also because of course there are some sections I've suggested to be split for which target pages need to be identified if possible. ~ Keiji (iNVERTED) (Talk) 21:00, 18 November 2011 (UTC)

By the way, feel free to reply in-line with my comments on each section above, but please copypaste my signature there if you do to avoid it becoming a mess. ~ Keiji (iNVERTED) (Talk) 21:02, 18 November 2011 (UTC)

Thanks for your suggestions Keiji!! :) Actually i did make a new page, solely on Applications of Stack, not once, but twice, but that was deleted both the times.. So i had to suffice by putting up all the information here.. I did give the same reason for creating a new page, stating that this page is looking really messy, but that reason did not seem sufficient.. Nipun Bayas (talk) 14:09, 5 January 2012 (UTC)

Hi Nipun. I think the application section is—at least in its current form—is not suited for an encyclopedic article on stacks. It would be more appropriate for a textbook, such as the WikiBook on data structures. One or two of the applications could remain (parsing expression is a classical example of the use of stacks, so that would be a good choice), be would need to be made more concise and probably use pseudocode. —Ruud 18:06, 21 August 2012 (UTC)

It's absurdly long - this is a problem with Wikipedia - people can put more and more in, but try to take out the garbage and you're blocked because you're "vandalizing the article. — Preceding unsigned comment added by 75.79.3.43 (talk) 20:41, 16 May 2014 (UTC)

incorrect step in expression-evaluation section?[edit]

I'd prefer if somebody more knowledgeable about this topic fixed this, but I think there may be a mistake in this section: Stack_(abstract_data_type)#Evaluation_of_an_infix_expression_that_is_fully_parenthesized. Under the "closing brackets" part, the step "Go to step (2.4)" seems wrong. It should be "Go to step (1)". You can't pop from the character stack unless you're ready to evaluate thanks to a closing parenthesis, right? Proxyma (talk) 04:04, 24 November 2013 (UTC)

Towers of Hanoi[edit]

Given (as stated) that there is a separate article on the algorithm, the lengthy text and numerous illustrations are way over the top - assuming this section should even be kept in the article.

"The linked-list implementation is equally simple and straightforward. "[edit]

Seriously? - double indirection is as simple and straightforward as single indirection.

The push and pop code both call an alleged function called empty() - no such C built-in.