Essentially a shop that, for several reasons, may be convenient for customers. Of course, what a Convenience Store actually is varies greatly.
A Convenience Store in some ways is akin to a Corner Shop, a Newsagents or a Supermarket, though size, content and style may differ. Examples of a Supermarket would be, for those of us who live in the UK at least, Tesco, Sainsburys or Asda. Examples of both Newsagents and Corner Shops are slightly more difficult to define, varying not only regionally and from town to town but often from different localities within a town itself, though the common concept of both of these remains a small, local shop for local people; in general one may be able to purchase basic foods and daily newspapers within, but one would not drive from another locality to do so as you would to an 'out of town' Supermarket.
Convenience Stores, just as with Newsagents and Corner Shops, will vary regionally, though will more often be managed by specific companies. An example would be 'Jacksons' stores, which are common in Yorkshire but non-existent in Sussex, and vica versa for 'Dillons'.
Because of their Convenient nature, shops of this type will often be open from early in the morning until late at night - the '7/11', for example, draws its name from its opening hours. In essence, they could be pictured as small Supermarkets, though since the definition of a Supermarket is currently in flux, with the larger companies branching out into electrical goods as well as the more common foodstuffs, this is a difficult and misleading description.
Convenience Stores could therefore be supposed to be convenient for different reasons to different people. A small Supermarket located in a village fifteen miles from the nearest town would be convenient to the villagers, but not to people living in the distant towns. Likewise, a store open until 11.30pm in the middle of town would be convenient to night-time revellers for its supply of cigarettes and alcohol. As the circumstances change, so would the nature of the convenience to customers.