0

I am trying to find the source code for the earliest implementation of the stack data structure in C, but I can't find anything.

I am particularly interested in knowing if the member variables of the stack data structure were made private, or if they were kept public (and so it was the job of the programmer not to modify these variables by accident).

Note: If the source code for the stack data structure is not available, I am also interested in the source codes of other data structures like queue and linked list and so on.

  • 7
    There is no notion of data hiding in the C language. – Leo B. Apr 6 at 5:40
  • 7
    Are you talking about the call stack that is used implicitly or are you asking about something implemented in user space? Because if you're talking about the former, you just need to unearth the implementation of the very first version of the original K&R C implementation (ca. 1978). – DarkDust Apr 6 at 6:12
  • 4
    ... and if you talk about user space, a simple stack implementation is trivial, so there's probably no record of it. Note that the idea of a stack data structure is much older, going back to at least 1957. – Michael Graf Apr 6 at 8:01
  • 2
    You should edit your question to make it clear about what kind of stack you are asking. And decide which language you mean, C++ STL has nothing to do with C. – the busybee Apr 6 at 11:20
  • 2
    There is no encapsulation and no "stack data structure" in C. – peterh - Reinstate Monica Apr 6 at 14:49
6

I am trying to find the source code for the earliest implementation of the stack data structure in C

There is no stack data structure in C. Look through the language specification and you won't find it there. If you were a programmer and you wanted a stack, you had to implement your own. If you go back to the beginnings of C and look at all the code that needed a stack, you'll probably find that there were as many implementations as there were stacks.

There are many ways to implement a stack in C. Perhaps the easiest is as an array and an index

int intStack[STACK_SIZE];
int stackPointer = 0;

void push(int newElement) 
{
    intStack[stackPointer++] = newElement;
}

int pop() 
{
    return intStack[--stackPointer];
}

Two points about the above:

  1. I'm using modern syntax. I can barely remember how to write K&R C, so I'm not even going to try.
  2. There are no checks for stack overflow or underflow. It would complicate the code and there were probably plenty of stacks written without bounds checks anyway.

The above implementation is very similar to a stack defined in K&R The C Programming Language in chapter 4 which probably counts as a fairly early example of a stack.

I am particularly interested in knowing if the member variables of the stack data structure were made private, or if they were kept public

That would depend on the quality of the programmer. Contrary to popular belief, C does have data hiding. In fact, I would argue that it is better than C++1. However, there's no qualification of structure members by access keywords. Data hiding has to be done at the compilation unit (file) level and is all or nothing. Here's how:

Firstly, you need to put the elements of your stack and the pointer into a struct in a separate source file.

/* intstack.c */

#include "intstack.h" /* See below for what is in here */

struct IntStack
{
    int data[STACK_SIZE];
    int pointer;
}

void IntStack_push(struct IntStack *stack, int newElement) 
{
    stack->data[stack->pointer++] = newElement;
}

int IntStack_pop(struct IntStack *stack) 
{
    return stack->data[--stack->pointer];
}

struct IntStack *IntStack_new()
{
    return calloc(1, sizeof(struct IntStack));
} 

void IntStack_delete(struct IntStack *stack)
{
    free(stack);
}

Then you need a header file that has prototypes of all the functions and an incomplete declaration of the struct

/* intstack.h */

struct IntStack; /* Incompleter declaration */

void IntStack_push(struct IntStack *stack, int newElement); 

int IntStack_pop(struct IntStack *stack); 

struct IntStack *IntStack_new();

void IntStack_delete(struct IntStack *stack);

Other people can use your stack by simply including the header file. They have no access to the internal members of the struct (well, not without doing something bad casting pointers to the struct to some other type).

#include "intstack.h"

int main()
{
    struct IntStack *stack = IntStack_new();

    IntStack_push(stack, 3);
    printf("%d\n", IntStack_pop()); /* prints 3 */
    IntStack_delete(stack);

    return 0;
}

I am also interested in the source codes of other data structures like queue and linked list and so on.

Similar comments to the above are applicable2. Incidentally, a singly linked list is pretty much the same as a dynamically growing stack i.e. one that doesn't overflow until the memory runs out.


1 In C++ you haver to put the private members in a class declaration in a header which means the protections can be defeated simply by #define private public before the header is included.

2 Some operating systems have implementations of queues e.g. macOS has a number of library functions and macros to implement queues of various types.

| improve this answer | |
  • 1
    In K&R, signatures are different (i.e. practically non-existent); don't put types on parameters inside the ()'s. If you want types they go after the () and before the first {, and are effectively part of the implementation not the signature. There's also no void keyword. – Erik Eidt Apr 6 at 16:08
  • 2
    +1 for to your first footnote! – Mike Spivey Apr 6 at 19:44
  • I think you miss the point of data hiding. It's protection against Murphy, not against Machiavelli. #define private public is definitely Machiavelli. To protect against Machiavelli, you need encryption, not data hiding. – MSalters Apr 7 at 11:10
  • @MSalters Nope. I don't. There are levels of Machiavelli ranging from person trying to hack your system to lazy incompetent programmer looking for a short cut. Furthermore, there are some technical aspects in which the C way is superior e.g. you can change the internal implementation without having to recompile everything that uses the API. – JeremyP Apr 8 at 8:13
3

As mentioned in the comments, data can’t be entirely hidden in C, there is no concept of “public” v. “private” members of data structures. Members can be hidden in practice using pointers to opaque data structures (see for example FILE), but that’s only a “gentleman’s agreement”.

When looking for early implementations in C, your best bet is to dig in the early Unix code. For example, here’s an early linked list (Research V4, August 1973):

struct cblock {
    struct cblock *c_next;
    char info[6];
};

The same release already had dc, which manipulates a stack, but it was written in assembly; its C implementation in V7 (1979) has a stack, although it’s probably not the earliest implementation of a stack in C:

struct  blk *stack[STKSZ];
struct  blk **stkptr,**stkbeg;
struct  blk **stkend;
int stkerr;

In fact an earlier implementation can be seen in the C compiler in V6 (1975):

    struct tnode *expstack[20];
    register struct tnode **sp;

As is commonly the case in C, the stack isn’t implemented as an explicit data structure (struct), but as an array and a pointer, with bounds-checking (albeit after-the-fact in this case).

| improve this answer | |
2

My understanding is that the stack is provided at the architectural level, eg it is built in to the processor in the form of a stack pointer and relevant operators. It is not a language level concept, in the way that other data structures may be.

| improve this answer | |
  • 1
    The fact that the CPU manages a stack doesn’t mean that other stacks can’t be useful too, and end up being implemented in all languages... – Stephen Kitt Apr 6 at 8:02
  • 2
    I think we're not clear enough what we're talking about here. As @DarkDust noted above, there's the call stack, and there's the stack (LIFO) data structure in user space. If we're talking about the call stack, some systems do support a call stack in hardware, some don't, and some do it in such a limited way that it's not really useful for C anyway. – Michael Graf Apr 6 at 8:04
  • 1
    I am reading into the question asking about 'the stack' as opposed to 'a stack'. The question only makes sense if refers to a common stack structure shared between routines. – Mark Williams Apr 6 at 8:09
  • See my answer for an example of a stack shared between routines. However like most C stacks it’s not a separate data structure, but an array and pointers into the array. – Stephen Kitt Apr 6 at 8:16
  • 1
    There's no requirement for the activation record stack ("call stack") to be supported in the hardware. There have been language implementations that use a stack on machines that don't have a stack. All you need is storage and a pointer. The pointer doesn't even have to be a register. – another-dave Apr 6 at 22:35
1

I'm probably repeating other posts, but let me try and summarize.

  1. There is no 'stack' in the definition of the C language

  2. An implementation of C very likely uses a stack for activation records (holding local variables and return addresses, for example) -- also known as a 'call stack'.

  3. The C standard library has no 'stack' data structure

  4. The concept of 'stack' is much older than C (and older than settling on the word 'stack' as the name to use)

  5. There were surely countless private implementations of a stack structure in C; it's so simple.

| improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.